﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BL.objects
{
    class Graph
    {
        List<Node> m_Nodes;
        List<NodesEdge> m_Edges;

        public Graph(List<Edge> edges)
        {
            m_Nodes = new List<Node>();
            m_Edges = new List<NodesEdge>();

            foreach (Edge edge in edges)
            {
                Node node, node2;

                node = getNode(edge.InVertex);
                node2 = getNode(edge.OutVertex);

                m_Edges.Add(new NodesEdge(node, node2, edge));
            }
        }

        private Node getNode(Vertex vertex)
        {
            var query = from n in m_Nodes
                        where n == vertex
                        select n;

            if (query.Count() > 0)
                return query.First();
            else
            {
                Node node = new Node(vertex);
                m_Nodes.Add(node);
                return node;
            }
        }

        public List<Node> FindShortestPath(int from, int to)
        {
            Node fromNode = m_Nodes.Find(node => node.Id == from);
            Node toNode = m_Nodes.Find(node => node.Id == to);

            return findShortestPath(fromNode, toNode);
        }

        private List<Node> findShortestPath(Node from, Node to)
        {
            foreach (Node node in m_Nodes)
            {
                node.Clear();
            }

            Node srcNode = m_Nodes.Find(node => node == from);
            srcNode.Cost = 0;

            Node currentNode = srcNode;
            currentNode.Visited = true;

            do
            {
                Node nextBestNode = null;

                var visitedNodes = from node in m_Nodes
                                   where node.Visited
                                   select node;

                foreach (Node node in m_Nodes)
                {
                    var edges =    from edge in m_Edges
                                            where edge.EligibleForNodeTraverse(node)
                                            select edge;

                    foreach (NodesEdge edge in edges)
                    {
                        Node secondNode = edge.GetSecondNode(node);
                        if (secondNode.UnInitialized || (node.Cost + edge.Weight < secondNode.Cost))
                        {
                            secondNode.Update(node.Cost + edge.Weight, edge);
                        }

                        if (nextBestNode == (object)null || secondNode.Cost < nextBestNode.Cost)
                        {
                            nextBestNode = secondNode;
                        }
                    }        
                }
                
                currentNode = nextBestNode;
                currentNode.Visited = true;

            } while (m_Nodes.FindAll(n => !n.Visited).Count > 0);

            List<Node> shortestPath = new List<Node>();

            currentNode = m_Nodes.Find(node => node == to);

            shortestPath.Add(currentNode);

            while (currentNode.BestEdge != null)
            {
                currentNode = currentNode.BestEdge.GetSecondNode(currentNode);
                shortestPath.Add(currentNode);
            }            
            
            shortestPath.Reverse();

            return shortestPath;
        }
    }
}
